package org.example;

import java.util.*;

public class Test3 {
    //leetcode 字母异位词分组
    //https://leetcode.cn/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-interview-150

    /**
     * 超时，一组测试用例未过
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> ret = new ArrayList<>();
        ret.add(new ArrayList<>());
        ret.get(0).add(strs[0]);
        for (int i = 1; i < strs.length; i++) {
            boolean flg = false;
            for (int j = 0; j < ret.size(); j++) {
                String s = ret.get(j).get(0);
                if (isAnagram(s,strs[i])) {
                    ret.get(j).add(strs[i]);
                    flg= true;
                    break;
                }
            }
            if (!flg) {
                ret.add(new ArrayList<>());
                ret.get(ret.size()-1).add(strs[i]);
            }
        }
        return ret;
    }

    private boolean isAnagram(String s, String t) {
        int[] hash = new int[26];
        for (char c : s.toCharArray()) {
            hash[c-'a']++;
        }
        for (char c : t.toCharArray()) {
            if (hash[c-'a']-- == 0) return false;
        }
        for (int i = 0; i < 26; i++) {
            if (hash[i] != 0) return false;
        }
        return true;
    }

    /**
     * 通过
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams1(String[] strs) {
        //既然是字母异位词，那么他们就是由相同的字母组成并且字母的数量也是相同的
        //那么也就意味着为单词异位词的两个单词的根据字典序排序之后的结果是相同的
        //所以我们就可以将单词根据字典序排序的结果作为key，
        // 然后遍历单词的时候将其根据字典序排序之后，看hash中是否存在
        Map<String,List<String>> hash = new HashMap<>();
        for (String s : strs) {
            char[] tmp = s.toCharArray();
            Arrays.sort(tmp);
            String key = new String(tmp);
            if (!hash.containsKey(key)) {
                hash.put(key,new ArrayList<>());
            }
            hash.get(key).add(s);
        }
        return new ArrayList(hash.values());
    }
    public static void main(String[] args) {
        List<List<String>> ret = new ArrayList<>();
        ret.add(new ArrayList<>());
        String s = "abcd";
        Map<String,String> hash = new HashMap<>();
    }
}
